
\section{Perturbing the weight of edges.}
The goal of this step is to ensure that the shortest path \(S[x,y]\) between vertices \(x\) and \(y\) is unique. This property allows unambiguous construction of \emph{arc-short circuits} from a digraph. If \(w(e)\) describes original weight of the edge, \(E\) -- set of all graph edges, \(V\) --- set of all vertices contained by the graph, the perturbance function is equal to: 
\begin{equation}
        dw(e_i) = w(e_i) + \varepsilon * 3^{-i} - pm(|E|,\varepsilon)
\end{equation} 
\begin{equation}
        \varepsilon = \cfrac{0,5}{|E||V|}
\end{equation}

\noindent Perturbance modification (modification of original Gleiss algorithm): 
\begin{equation}
        pm(|E|,\varepsilon) = \cfrac{2 * diff}{|E|}
\end{equation} 
is designed to remove the risk that the perturbance will affect \emph{Dijkstra} algorithm and is only applied in case the value of: 
\begin{equation}
        diff = \sum_{i=0}^{|E|-1} \varepsilon * 3^{-i} - w(e)_{min}
\end{equation} 
\begin{equation}
        diff = \varepsilon * \cfrac{1 - 3^{-|E|}}{1 - 3^{-1}} - w(e)_{min}
\end{equation} 
is greater or equal zero.

\section{Construction of \emph{arc-short circuits}.}
Although it is possible to list all the circuits in a graph, it is usually computationally challenging because of the number of circuits. In this algorithm we use the set of so called \emph{arc-short circuits} that create the \emph{Horton set}. It was shown in \cite{pub:Horton} that this set contains the minimal cycle basis but not all cycle bases. We use \emph{Dijkstra} algorithm to find all the shortest paths in the input graph. 

\emph{Arc-short circuit} is constructed for each edge \((x,y)\) and vertice \(z\):

\begin{equation}
        A_i = (x,y) + S[y,z] + S[z,x] 
\end{equation}

no vertice can appear in the arc-short circuit more than once.

\section{Minimal circuit base extraction with \emph{R-greedy} algorithm.}
The final result (minimal circuit base and relevant circuits) is calculated by sorting the elements of input \emph{graph circuit matroid} basis and finding its lineary independent subsets \emph{on-fly}. For the result of the \emph{independent(1)} function in \ref{code:RGreedy} we use the \emph{Gauss-Jordan elimination} algorithm.  

\lstset{caption={\emph{R-Greedy} algorithm implementation in \emph{Python} language.}, label={code:RGreedy}}
\begin{lstlisting}[frame=tb]
def r_greedy(circuits):
	circuits.sort(key = attrgetter("weight"))
	b_less = []
	relevant = []
	prev_circuit = circuits[0]
	r_equal = [prev_circuit]
	b_equal = [prev_circuit]
	for circuit in circuits[1:]:
		if circuit.weight > prev_circuit.weight:
			relevant.extend(r_equal)
			b_less.extend(b_equal)
			r_equal = [circuit]
			b_equal = [circuit]
		else:
			if independent([circuit] + b_less):
				r_equal.append(circuit)
			if independent([circuit] + b_less + b_equal):
				b_equal.append(circuit)
		prev_circuit = circuit
	relevant.extend(r_equal)
	b_less.extend(b_equal)
	return (b_less, relevant)

\end{lstlisting}

\section{Computational complexity}
Algorithm has the following complexity~\cite{pub:Gleiss}:
\begin{equation}
O(v(G)|E|^{2}|V|)
\end{equation}
\begin{equation}
v(G) = |E| - |V| + c(G)
\end{equation}
\noindent where $c(G)$ denotes the number of weak components of graph $G$.
